public class SolutionInterview8_1 {
    public int waysToStep(int n) {
        if (n==1){
            return 1;
        }else if (n==2){
            return 2;
        }else if (n==3){
            return 4;
        }else {
            long d=-1,a=1,b=2,c=4;
            for (int i=4;i<=n;i++){
                d=(a+b+c)%1000000007;
                a=b;
                b=c;
                c=d;
            }
            return (int)d;
        }
    }

    public static void main(String[] args) {
        System.out.println(new SolutionInterview8_1().waysToStep(5));
    }
}
